import time
st = time.time()

from fractions import Fraction

uplimit = 10 ** 6
all_primes = [1] * (uplimit + 1)

primes = []
index = 2
endprint = 0
while index <= uplimit:
    if all_primes[index]:  # 本身是质数
        primes.append(index)
        k = 2 * index
        while k <= uplimit:
            all_primes[k] = 0
            k += index
        all_factors = [index]
    else:  # 本身是合数
        tmp = index
        all_factors = []
        limit = int(1 / 2 * index) + 1
        for prime in primes:
            if prime > limit:
                break
            while 0 == tmp % prime:
                all_factors.append(prime)
                tmp = tmp // prime
    prime_factor = set(all_factors)
    ress = index
    for fac in prime_factor:
        ress = ress * (1-Fraction(1,fac))
    endprint += ress
    print("%d的质因数共有：%d个" % (index,ress))
    index += 1

print(endprint)

print(time.time() - st)